/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: test_btree.c 32 2009-10-28 22:51:19Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <malloc.h>

#include <CUnit/Basic.h>

#include "../src/btree.h"
#include "../src/function_prototypes.h"

#include "test_helpers.h"
#include "test_btree.h"

Btree *bst, *rb;

int
init_test_btree_suite ()
{
  bst = btree_create (&comp_char, BST);
  if (bst == NULL)
    return 1;

  rb = btree_create (&comp_char, RB);
  if (rb == NULL)
    {
      btree_destroy (bst, &dest_char);
      return 1;
    }

  return 0;
}

int
clean_test_btree_suite ()
{
  btree_destroy (bst, &dest_char);
  btree_destroy (rb, &dest_char);

  return 0;
}

void
test_btree_inserts ()
{
  char *i, *x;
  char failures[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
  int cur;

  /* Standard insert. */
  for (cur = 0; cur < 10; cur++)
    {
      i = malloc_char ('A' + cur);
      if (i == NULL)
	{
	  CU_FAIL ("malloc i failed.");
	  continue;
	}

      x = btree_insert (bst, i);
      CU_ASSERT (x != NULL);
      CU_ASSERT (x == i);

      CU_ASSERT (btree_size (bst) == cur + 1);
    }

  /* Standard failures. */
  for (cur = 0; cur < 10; cur++)
    {
      x = btree_insert (bst, &(failures[cur]));
      CU_ASSERT (x != NULL);
      CU_ASSERT (x != &(failures[cur]));

      CU_ASSERT (btree_size (bst) == 10);
    }


  /* Standard insert. */
  for (cur = 0; cur < 10; cur++)
    {
      i = malloc_char ('A' + cur);
      if (i == NULL)
	{
	  CU_FAIL ("malloc i failed.");
	  continue;
	}
      
      x = btree_insert (rb, i);
      CU_ASSERT (x != NULL);
      CU_ASSERT (x == i);

      CU_ASSERT (btree_size (rb) == cur + 1);
	    
    }

  /* Standard failures. */
  for (cur = 0; cur < 10; cur++)
    {
      x = btree_insert (rb, &(failures[cur]));
      CU_ASSERT (x != NULL);
      CU_ASSERT (x != &(failures[cur]));

      CU_ASSERT (btree_size (rb) == 10);
    }
}

void
test_btree_finds ()
{
  char c;
  int cur;

  /* Standard finds. */
  for (cur = 0; cur < 10; cur++)
    {
      c = 'A' + cur;

      CU_ASSERT (*((char *)btree_find (bst, &c)) == ('A' + cur));
      CU_ASSERT (*((char *)btree_find (rb, &c)) == ('A' + cur));
      CU_ASSERT (btree_size (bst) == 10);
      CU_ASSERT (btree_size (rb) == 10);
    }

  for (cur = 0; cur < 10; cur++)
    {
      c = 'L' + cur;

      CU_ASSERT (btree_find (bst, &c) == NULL);
      CU_ASSERT (btree_find (rb, &c) == NULL);
      CU_ASSERT (btree_size (bst) == 10);
      CU_ASSERT (btree_size (rb) == 10);
    }

}

void
test_btree_remove ()
{
  char *c, x;

  x = 'A';
  c = btree_remove (bst, &x);
  CU_ASSERT (c != NULL);
  CU_ASSERT (*c == 'A');
  CU_ASSERT (btree_size (bst) == 9);
  free (c);

  x = 'J';
  c = btree_remove (bst, &x);
  CU_ASSERT (c != NULL);
  CU_ASSERT (*c == 'J');
  CU_ASSERT (btree_size (bst) == 8);
  free (c);

  x = 'E';
  c = btree_remove (bst, &x);
  CU_ASSERT (c != NULL);
  CU_ASSERT (*c == 'E');
  CU_ASSERT (btree_size (bst) == 7);
  free (c);

  x = 'Z';
  c = btree_remove (bst, &x);
  CU_ASSERT (c == NULL);
  CU_ASSERT (btree_size (bst) == 7);

  x = 'M';
  c = btree_remove (bst, &x);
  CU_ASSERT (c == NULL);
  CU_ASSERT (btree_size (bst) == 7);

  x = 'Q';
  c = btree_remove (bst, &x);
  CU_ASSERT (c == NULL);
  CU_ASSERT (btree_size (bst) == 7);


  x = 'A';
  c = btree_remove (rb, &x);
  CU_ASSERT (c != NULL);
  CU_ASSERT (*c == 'A');
  CU_ASSERT (btree_size (rb) == 9);
  free (c);

  x = 'J';
  c = btree_remove (rb, &x);
  CU_ASSERT (c != NULL);
  CU_ASSERT (*c == 'J');
  CU_ASSERT (btree_size (rb) == 8);
  free (c);

  x = 'E';
  c = btree_remove (rb, &x);
  CU_ASSERT (c != NULL);
  CU_ASSERT (*c == 'E');
  CU_ASSERT (btree_size (rb) == 7);
  free (c);

  x = 'Z';
  c = btree_remove (rb, &x);
  CU_ASSERT (c == NULL);
  CU_ASSERT (btree_size (rb) == 7);

  x = 'M';
  c = btree_remove (rb, &x);
  CU_ASSERT (c == NULL);
  CU_ASSERT (btree_size (rb) == 7);

  x = 'Q';
  c = btree_remove (rb, &x);
  CU_ASSERT (c == NULL);
  CU_ASSERT (btree_size (rb) == 7);
}

void
test_btree_traverser ()
{
  BtreeTraverser trav;
  char *c;
  int count;

  count = 0;
  btree_traverser_init (&trav, bst);
  while ((c = btree_traverser_next (&trav)) != NULL)
    {
      if (*c == 'F')
	count++;

      CU_ASSERT (*c == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (btree_size (bst) == 7);
      count++;
    }
  
  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (bst) == 7);

  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (bst) == 7);

  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (bst) == 7);

  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (bst) == 7);

  count = 0;
  btree_traverser_init (&trav, bst);
  while ((c = btree_traverser_prev (&trav)) != NULL)
    {
      if (*c == 'D')
	count--;

      CU_ASSERT (*c == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (btree_size (bst) == 7);
      count--;
    }

  count = 0;
  btree_traverser_init (&trav, rb);
  while ((c = btree_traverser_next (&trav)) != NULL)
    {
      if (*c == 'F')
	count++;

      CU_ASSERT (*c == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'B' + count);
      CU_ASSERT (btree_size (rb) == 7);
      count++;
    }
  
  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (rb) == 7);

  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (rb) == 7);

  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (rb) == 7);

  CU_ASSERT (*((char *)btree_traverser_first (&trav)) == 'B');
  CU_ASSERT (*((char *)btree_traverser_last (&trav)) == 'I');
  CU_ASSERT (btree_size (rb) == 7);

  count = 0;
  btree_traverser_init (&trav, rb);
  while ((c = btree_traverser_prev (&trav)) != NULL)
    {
      if (*c == 'D')
	count--;

      CU_ASSERT (*c == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (*((char *)btree_traverser_cur (&trav)) == 'I' + count);
      CU_ASSERT (btree_size (rb) == 7);
      count--;
    }
}

int
make_btree_suite (CU_pSuite s)
{
  s = CU_add_suite ("Test Btree Suite", 
		    init_test_btree_suite, 
		    clean_test_btree_suite);
  if (s == NULL)
    {
      return CU_get_error();
    }

  if (CU_add_test (s, "test btree_insert's", test_btree_inserts) == NULL ||
      CU_add_test (s, "test btree_finds's", test_btree_finds) == NULL ||
      CU_add_test (s, "test btree_remove's", test_btree_remove) == NULL ||
      CU_add_test (s, "test btree_traverser's", test_btree_traverser) == NULL
      )
    {
      return CU_get_error();
    }

  return CU_get_error();
}
